#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

/**
 * 291 滑动窗口 + 查找表
 * 时间复杂度O(n)
   空间复杂度O(k)
 **/
class Duplicate{
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
 		// 使用映射记录  
		unordered_set<int> record;
		// 滑动窗口长度固定 就是record长度,保证record 大小在k+1内
		for(int i = 0; i < nums.size();i++){
			// 当前窗口 添加新元素后是否出现满足题意数据对
			// 查找表查找是否存在当前要添加元素
			if(record.find(nums[i]) != record.end()){
				return true;
			}
			// 否则新元素和滑动窗口任何数据都不重复
			record.insert[nums[i]];

			// 判断当前滑动窗口大小, 保证record中有k个元素
			if(record.size() == k + 1){
				record.erase(nums[i - k]);
			}
		}       
		return false;
    }

};
